package com.xupt.top;

/**
 * @author zhaoxin
 * @title: ConvertBST
 * @projectName LeetCode
 * @description: 538. 把二叉搜索树转换为累加树
 * @date 2019/12/16 11:09
 */
public class ConvertBST {
    /**
     *给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
     *
     * 例如：
     *
     * 输入: 二叉搜索树:
     *               5
     *             /   \
     *            2     13
     *
     * 输出: 转换为累加树:
     *              18
     *             /   \
     *           20     13
     *
     * @param root
     * @return
     */
    private int rightSum = 0;

    /**
     * 1) 先将右子树转换为累加树；并记录右子树的累加和rightSum;
     * 2) 然后处理根节点，根节点的值 = 根节点值 + rightSum;
     * 3) 转换左子树
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null){
            return null;
        }
        convertBST(root.right);
        root.val = root.val + rightSum;
        rightSum = root.val;
        convertBST(root.left);
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(13);
        ConvertBST convertBST = new ConvertBST();
        convertBST.convertBST(root);

    }


}
